package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/4/6.
 *
 * 连续子数组最大和
 */
public class TestProblem42 {

    /**
     * 动态规划
     * @param array
     * @param
     * @return
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        /**
         * 公式 max(dp[i]) = getMax(max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )
         * 上面式子的意义是：我们从头开始遍历数组，遍历到数组元素 arr[ i ] 时，
         * 连续的最大的和 可能为 max( dp[ i -1 ] ) + arr[ i ] ，
         * 也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n
         */
        if (array == null || array.length < 1) return 0;
        int sum = array[0];
        int max = array[0];
        for (int i = 1;i < array.length;i++) {
            sum = getMax (sum + array[i],array[i]);
            if(sum >= max)
                max = sum;
        }
        return max;
    }

    public int getMax (int a,int b) {
        return a > b ? a : b;
    }

    /*if(array.length==0)return 0;
             
                    for(int i = 1 ; i < array.length; i++)
                        if(array[i-1]>0) 
                            array[i] += array[i-1];
                 
                    int max = array[0];
            for(int i = 1 ; i < array.length; i++)
                        if(array[i] > max)max = array[i];
                 
                    return max;*/
    /*int maxResult = A[0];
    int maxTemp = 0;
    for(int i = 0;i < A.length;i++){
        if(maxTemp >= 0)
            maxTemp += A[i];
        else
            maxTemp = A[i];
        if(maxTemp > maxResult)
            maxResult = maxTemp;
    }
    return maxResult;*/

    public static void main(String args[]){

    }
}
